package com.datastructures2.不相交集类;

/**
 *
 * @author MaoLin Wang
 * @date 2020/2/2021:16
 */
public class DisjSets {
    private int[] s;

    /**
     * 数组初始化为-1，s[i] 表示元素i的父亲
     * @param numElements
     */
    public DisjSets(int numElements) {
        s=new int[numElements];
        for (int i = 0; i < numElements; i++) {
            s[i]=-1;
        }
    }

    /**
     * 合并两个不相交集类 -----基本数据结构
     * @param root1
     * @param root2
     */
    public void unionBase(int root1,int root2){
        s[root2]=root1;
    }

    /**
     * 按高度求并
     * @param root1
     * @param root2
     */
    public void unionByHeight(int root1,int root2){
        if (s[root2]<s[root1]){
            s[root1]=root2;
        }else {
            if (s[root1]==s[root2]){
                s[root1]--;
            }
            s[root2]=root1;
        }
    }
    public int find(int x){
        if (s[x]<0){
            return x;
        }else {
            return find(s[x]);
        }
    }

    /**
     * 路径压缩
     * @param x
     * @return
     */
    public int findByPathCompression(int x){
        if (s[x]<0){
            return x;
        }else {
            return s[x]=find(s[x]);
        }
    }

}
